package top.ivansong92.example.leetcode.learning.data.struct.stack;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

public class TestExamp {

    @Test
    public void test1() {
        String s = "/home//foo/";
        System.out.println(Arrays.stream(s.split("/")).collect(Collectors.joining(",")));
    }

    @Test
    public void testisValidV2() {
        System.out.println(isValidV2("()"));
    }
    public boolean isValidV2(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        if (s.length() % 2 != 0) {
            return false;
        }

        LinkedList<Character> charStack = new LinkedList<>();
        for (char ch : s.toCharArray()) {
            switch (ch) {
                case '(':
                case '[':
                case '{':
                    charStack.push(ch);
                    break;
                case ')':
                    if (charStack.isEmpty() || charStack.pop() != '(') {
                        return false;
                    }
                    break;
                case ']':
                    if (charStack.isEmpty() || charStack.pop() != '[') {
                        return false;
                    }
                    break;
                case '}':
                    if (charStack.isEmpty() || charStack.pop() != '{') {
                        return false;
                    }
                    break;
                default:
                    return false;
            }
        }

        return charStack.isEmpty();
    }
    /**
     * 20. 有效的括号
     * https://leetcode-cn.com/problems/valid-parentheses/
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        LinkedList<Character> list = new LinkedList<>();
        char[] chars = s.toCharArray();
        for(char ch : chars) {
            switch (ch) {
                case '[':
                case '(':
                case '{':
                    list.push(ch);
                    break;
                case ']':
                    if (list.size() == 0) {
                        return false;
                    }
                    char k1 = list.pop();
                    if (k1 != '[') {
                        return false;
                    }
                    break;
                case ')':
                    if (list.size() == 0) {
                        return false;
                    }
                    char k2 = list.pop();
                    if (k2 != '(') {
                        return false;
                    }
                    break;
                case '}':
                    if (list.size() == 0) {
                        return false;
                    }
                    char k3 = list.pop();
                    if (k3 != '{') {
                        return false;
                    }
                    break;
            }
        }

        return list.size() == 0;
    }

    public boolean isValid2(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for(char ch : chars) {
            switch (ch) {
                case '[':
                case '(':
                case '{':
                    stack.push(ch);
                    break;
                case ']':
                    if (stack.size() == 0) {
                        return false;
                    }
                    char k1 = stack.pop();
                    if (k1 != '[') {
                        return false;
                    }
                    break;
                case ')':
                    if (stack.size() == 0) {
                        return false;
                    }
                    char k2 = stack.pop();
                    if (k2 != '(') {
                        return false;
                    }
                    break;
                case '}':
                    if (stack.size() == 0) {
                        return false;
                    }
                    char k3 = stack.pop();
                    if (k3 != '{') {
                        return false;
                    }
                    break;
            }
        }

        return stack.size() == 0;
    }

    /**
     * 150. 逆波兰表达式求值
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }

        LinkedList<String> stack = new LinkedList<>();
        int val1, val2;
        for (String s : tokens) {
            switch (s) {
                case "*":
                    if (stack.size() < 2) {
                        return 0;
                    }
                    val1 = Integer.parseInt(stack.pop());
                    val2 = Integer.parseInt(stack.pop());
                    stack.push((val1 * val2) + "");
                    break;
                case "/":
                    if (stack.size() < 2) {
                        return 0;
                    }
                    val1 = Integer.parseInt(stack.pop());
                    val2 = Integer.parseInt(stack.pop());
                    stack.push((val2 / val1) + "");
                    break;
                case "+":
                    if (stack.size() < 2) {
                        return 0;
                    }
                    val1 = Integer.parseInt(stack.pop());
                    val2 = Integer.parseInt(stack.pop());
                    stack.push((val2 + val1) + "");
                    break;
                case "-":
                    if (stack.size() < 2) {
                        return 0;
                    }
                    val1 = Integer.parseInt(stack.pop());
                    val2 = Integer.parseInt(stack.pop());
                    stack.push((val2 - val1) + "");
                    break;
                default:
                    stack.push(s);
                    break;
            }
        }
        return Integer.parseInt(stack.pop());
    }


    @Test
    public void test2() {
        String s = "/home//foo/";
        System.out.println(simplifyPath(s));
    }

    /**
     * 71. 简化路径
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
         String[] strings = path.split("/");
        LinkedList<String> stack = new LinkedList<>();
        for (String s : strings) {
            switch (s) {
                case ".":
                case "":
                    break;
                case "..":
                    if (stack.size() == 0) {
                        break;
                    }
                    stack.pop();
                    break;
                default:
                    stack.push(s);
                    break;
            }
        }

        if (stack.size() == 0) {
            return "/";
        }

        List<String> res = new ArrayList<>();
        for (int i = stack.size() - 1; i >= 0; i--) {
            res.add(stack.get(i));
        }
        return "/" + String.join("/", res);
    }

    /**
     * 面试题 16.26. 计算器
     * @param s
     * @return
     */
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        int num = 0;
        char op = '+';
        for (int i = 0; i <= s.length(); i ++) {
            if (i == s.length()) {
                switch (op) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        int top = stack.pop();
                        stack.push(top * num);
                        break;
                    case '/':
                        int val = stack.pop();
                        stack.push(val / num);
                        break;
                }
                break;
            }

            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            } else if (ch != ' ') {
                switch (op) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        int top = stack.pop();
                        stack.push(top * num);
                        break;
                    case '/':
                        int val = stack.pop();
                        stack.push(val / num);
                        break;
                }
                op = ch;
                num = 0;
            }
        }

        return stack.stream().mapToInt(Integer::intValue).sum();
    }



    /**
     *  144. 二叉树的前序遍历
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNodeOrder> nodeStack = new LinkedList<>();
        nodeStack.push(new TreeNodeOrder(1, root));

        while (!nodeStack.isEmpty()) {
            TreeNodeOrder order = nodeStack.pop();
            TreeNode node = order.node;
            if (order.order == 1) {
                if (node.left != null) {
                    nodeStack.push(new TreeNodeOrder(1, node.left));
                }

                if (node.right != null) {
                    nodeStack.push(new TreeNodeOrder(1, node.right));
                }
                nodeStack.push(new TreeNodeOrder(0, node));
            } else {
                res.add(node.val);
            }
        }
        return res;
    }

    private static class TreeNodeOrder {
        int order;//0 输出  1递归
        TreeNode node;

        public TreeNodeOrder(int order, TreeNode node) {
            this.order = order;
            this.node = node;
        }
    }

}


class NestedIterator implements Iterator<Integer> {
    private List<Integer> list;
    private int counter;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = new ArrayList<>();
        counter = 0;
        if (nestedList != null && !nestedList.isEmpty()) {

            LinkedList<NestedInteger> stack = new LinkedList<>();
            for (int i = nestedList.size() - 1; i >= 0; i--) {
                stack.push(nestedList.get(i));
            }

            while (!stack.isEmpty()) {
                NestedInteger node = stack.pop();
                if (node.isInteger()) {
                    list.add(node.getInteger());
                } else if (node.getList() != null && !node.getList().isEmpty()) {
                    for (int i = node.getList().size() - 1; i >= 0; i--) {
                        stack.push(node.getList().get(i));
                    }
                }
            }
        }
    }

    @Override
    public Integer next() {
        if (hasNext()) {
            return list.get(counter++);
        } else {
            return null;
        }
    }

    @Override
    public boolean hasNext() {
        return counter < list.size();
    }
}

interface NestedInteger {

    // @return true if this NestedInteger holds a single integer, rather than a nested list.
    boolean isInteger();

    // @return the single integer that this NestedInteger holds, if it holds a single integer
    // Return null if this NestedInteger holds a nested list
    Integer getInteger();

    // @return the nested list that this NestedInteger holds, if it holds a nested list
    // Return empty list if this NestedInteger holds a single integer
    List<NestedInteger> getList();
}
